package everydayGrade.t6;

/**
 * @Author: Siantar
 * @Date: 2023-10-24-11:02
 * @Description: 1.0
 */
public class T1155 {
    public int numRollsToTarget(int n, int k, int target) {
        int M = (int) 1e9 + 7;
        int[] ps = new int[target];
        for (int i = 0; i < k && i < target; i++) {
            ps[i] = 1;
        }
        for (int i = 0; i < n - 1; i++) {
            int[] ts = new int[target];
            for (int j = 0; j < k; j++) {
                for (int l = 0; l < target; l++) {
                    int s = j + 1 + l;
                    if (s < target) {
                        ts[s] = (ts[s] + ps[l]) % M;
                    }
                }
            }
            ps = ts;
        }
        return ps[target - 1];
    }
}
